/*
 * @lc app=leetcode.cn id=15 lang=javascript
 *
 * [15] 三数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    nums = quickSort(nums, 0, nums.length - 1)
    let ans = []
    for (let i = 0; nums[i] <= 0; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue //去重
        }
        let a = nums[i]
        let bPos = i + 1, cPos = nums.length - 1
        while (bPos < cPos && bPos <= nums.length - 2) {
            let b = nums[bPos], c = nums[cPos]
            if (a + b + c < 0) bPos++
            else if (a + b + c > 0) cPos--
            else {
                let item = [a, nums[bPos], nums[cPos]]
                ans.push(item)
                // 去重
                while (cPos > bPos && nums[bPos] == nums[bPos + 1]) bPos++
                while (cPos > bPos && nums[cPos] == nums[cPos - 1]) cPos--
                bPos++
                cPos--
            }
        }
    }
    return ans
};

function quickSort(arr, left, right) {
    if (left < right) {
        let pos = partition(arr, left, right)
        quickSort(arr, left, pos - 1)
        quickSort(arr, pos + 1, right)
        return arr
    } else {
        return arr
    }
}

function partition(arr, left, right) {
    let pivotPos = left
    let pivot = arr[left]
    for (let i = left + 1; i <= right; i++) {
        if (arr[i] < pivot) {
            pivotPos++
            if (pivotPos != i) {
                let t = arr[pivotPos]
                arr[pivotPos] = arr[i]
                arr[i] = t
            }
        }
    }
    arr[left] = arr[pivotPos]
    arr[pivotPos] = pivot
    return pivotPos
}
// @lc code=end
// @after-stub-for-debug-begin
module.exports = threeSum;
// @after-stub-for-debug-end